#pragma once

#pragma warning(disable:4715)

#include "Framework.h"
#include "ICollection.h"

namespace Framework
{
	template <class T>
	class _HELIX_FRAMEWORK_ITEM BinaryTree
		: public ICollection<T>
	{
	public:
		enum TraversalOrder
		{
			PreOrder,
			InOrder,
			PostOrder
		};
	private:
		class Node
		{
			friend class BinaryTree;
		public:
			Node(T value)
				: m_Left(NULL)
				, m_Right(NULL)
				, m_Parent(NULL)
				, m_Data(value)
				, m_Depth(0)
			{
			}

			~Node()
			{
			}

			T GetData()
			{
				return m_Data;
			}

			Node* GetLeft() const { return m_Left; }
			Node* GetRight() const { return m_Right; }
			Node* GetParent() const {return m_Parent; }
			Node* GetGrandParent() const
			{
				if(m_Parent)
				{
					return m_Parent->GetParent();
				}
				return NULL;
			}
			
			Node* GetSibling() const
			{
				if(m_Parent != NULL)
				{
					if(this == m_Parent->GetLeft()) return m_Parent->GetRight();
					else return m_Parent->GetLeft();
				}
				return NULL;
			}

			Node* GetUncle() const
			{
				Node* gp = GetGrandParent();
				if(gp != NULL)
				{
					if(gp->GetLeft() == this) return gp->GetRight();
					else return gp->GetLeft();
				}
				return NULL;
			}
			UInt32 GetDepth() const { return m_Depth; }
		protected:
			T m_Data;
			Node* m_Left;
			Node* m_Right;
			Node* m_Parent;
			UInt32 m_Depth;
		};
		class Enumerator
			: public IEnumerator<T>
		{
		public:
			Enumerator(BinaryTree* tree, const typename BinaryTree::TraversalOrder order)
				: m_Tree(tree)
				, m_TraversalOrder(order)
			{
			}

			~Enumerator()
			{
				int k = 0;
			}

			bool MoveNext()
			{
				return 1;
			}

			T Current()
			{
				return m_CurrentNode->GetData();
			}

			bool IsValid() 
			{ 
				return m_Tree != 0; 
			}
		protected:
			T Traverse(Node* node)
			{
				m_CurrentNode = node;
				switch(m_TraversalOrder)
				{
				case PreOrder:
					return node->GetData();
					if(node->GetLeft() != NULL) Traverse(node->GetLeft());
					if(node->GetRight() != NULL) Traverse(node->GetRight());
					break;
				case InOrder:
					if(node->GetLeft() != NULL) Traverse(node->GetLeft());
					return node->GetData();
					if(node->GetRight() != NULL) Traverse(node->GetRight());
					break;
				case PostOrder:
					if(node->GetLeft() != NULL) Traverse(node->GetLeft());
					if(node->GetRight() != NULL) Traverse(node->GetRight());
					return node->GetData();
					break;
				default:
					break;
				}
			}
			typename BinaryTree::TraversalOrder m_TraversalOrder;
			BinaryTree* m_Tree;
			Node* m_CurrentNode;
		};

		Node* m_Root;
		UInt32 m_Size;
	public:
		explicit BinaryTree()
			: m_Root(NULL)
			, m_Size(0)
			, m_TraversalOrder(InOrder)
		{
		}

		~BinaryTree()
		{
			Clear(m_Root);
		}

		void Clear(Node* node)
		{
			if(node != NULL)
			{
				Clear(node->GetLeft());
				Clear(node->GetRight());
				delete node;
			}
		}

		UInt32 Add(T data)
		{
			Node* n = BinaryInsert(data, m_Root);
			return n->GetDepth();
		}

		bool Remove(T item)
		{
			BinaryDelete(item, m_Root);
		}

		bool Contains(T item)
		{
			return (Find(item, m_Root) != NULL);
		}

		void CopyFrom(ICollection<T>& other)
		{
			IEnumerator<T>* e = other.GetEnumerator();
			while(e->MoveNext())
				Add(e->Current());
		}

		void CopyFrom(T* array, UInt32 elementCount)
		{
			for(UInt32 i=0; i < elementCount; ++i)
				Add(array[i]);
		}

		UInt32 Count()
		{
			return m_Size;
		}

		IEnumerator<T>* GetEnumerator()
		{
			return new Enumerator(this, m_TraversalOrder);
		}

		void SetTraversalOrder(const TraversalOrder order)
		{
			m_TraversalOrder = order;
		}

		Node* Find(T value, Node* start)
		{
			if(value < start->GetData())
			{
				if(start->GetLeft() != NULL)
					Find(value, start->GetLeft());
				else
					return NULL;
			}
			else if(value > start->GetData())
			{
				if(start->GetRight() != NULL)
					Find(value, start->GetRight());
				else
					return NULL;
			}
			else
			{
				return start;
			}
		}
	protected:
		TraversalOrder m_TraversalOrder;
		Node* GetInorderSuccessor(Node* node)
		{
		}
		Node* BinaryInsert(T value, Node* node)
		{
			// No root present, so just leave it at that
			if(!m_Root)
			{
				m_Root = new Node(value);
				return m_Root;
			}
			// otherwise, check left and right if the value is more or less than the children.
			if(value < node->m_Data)
			{
				if(node->GetLeft() != NULL)
					BinaryInsert(value, node->GetLeft());
				else
				{
					Node* l = new Node(value);
					l->m_Parent = node->GetLeft();
					node->m_Left = l;
					return l;
				}
			}
			else if(value >= node->m_Data)
			{
				if(node->GetRight() != NULL)
					BinaryInsert(value, node->GetRight());
				else
				{
					Node* r = new Node(value);
					r->m_Parent = node->GetRight();
					node->m_Right = r;
					return r;
				}
			}
		}
		Node* BinaryDelete(T value, Node* node)
		{
			if(node != NULL)
			{
				Node* successor = NULL;
				if(node->GetData() > item)
					node->m_Left = BinaryDelete(value, node->GetLeft());
				else if(node->GetData() < item)
					node->m_Right = BinaryDelete(value, node->GetRight());
				else
				{
					successor = GetInorderSuccessor(node);
					node->m_Data = successor->GetData();
					node->m_Right = BinaryDelete(successor->value, node->GetRight());
				}
				return node;
			}
			return NULL;
		}
	};
};